package datastructure;

import java.util.Arrays;

/**
 * O(1), route compression + union by size
 * 
 * @author yinzichen
 * 
 */
public class DisjointSet {
	int n;
	int[] f;

	public DisjointSet(int size) {
		n = size;
		f = new int[n];
		Arrays.fill(f, -1);
	}

	public int find(int u) {
		if (f[u] < 0) {
			return u;
		}
		f[u] = find(f[u]);
		return f[u];
	}

	public void union(int u, int v) {
		int f1 = find(u), f2 = find(v);
		if (f1 != f2) {
			if (f[f1] > f[f2]) {
				f[f2] += f[f1];
				f[f1] = f2;
			} else {
				f[f1] += f[f2];
				f[f2] = f1;
			}
		}
	}

}
